package com.fyl.basic_algorithm.sorts;

import java.util.LinkedList;

/**
 * @Description: 拓朴排序
 * @author:fyl
 * @date 2021/4/18 16:17
 * @Modified By:
 * @Modified Date:
 */
public class TopoSort {
    private int v;   //顶点的个数
    private LinkedList<Integer> adj[];  //邻接表

    public TopoSort(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {  //s先于t，边s->t
        adj[s].add(t);
    }

    /**
     * Kahn算法实现
     * 1.用inDegree数组统计每个顶点的入度，
     * 2.遍历inDegree将入度为0的顶点放入queue队列
     * 3.取出queue中的入度为0的顶点，遍历其后续指向顶点并将入度减1
     * 4.判断减去后的顶点入度是否为0，若为0放入队列，重复上述操作
     */
    public void topoSortByKahn() {
        int[] inDegree = new int[v];  //统计每个顶点的入度
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j);
                inDegree[w]++;
            }
        }

        LinkedList<Integer> queue = new LinkedList<>();
        //将入度为0的节点放入队列
        for (int i = 0; i < v; i++) {
            if (inDegree[i] == 0) queue.add(i);
        }

        while (!queue.isEmpty()) {
            //i节点为入度为0的节点
            int i = queue.remove();
            System.out.print("->" + i);
            //遍历i节点的后续节点
            for (int j = 0; j < adj[i].size(); j++) {
                int k = adj[i].get(j);
                //将后续节点的入度减1
                inDegree[k]--;
                //如果k节点的入度为0，放入队列
                if (inDegree[k] == 0) queue.add(k);
            }
        }
    }

    /**
     * DFS算法实现
     * 1.通过邻接表构造逆邻接表
     * 2.递归处理每个顶点，先输出顶点vertex依赖的顶点在输出自己
     */
    public void topoSortByDFS() {
        //先构建逆邻接表，边s->表示，s依赖于t，t优先于s
        LinkedList<Integer> inverseAdj[] = new LinkedList[v];
        //申请空间
        for (int i = 0; i < v; i++) {
            inverseAdj[i] = new LinkedList<>();
        }
        //通过邻接表生成逆邻接表
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j); //i->w
                inverseAdj[w].add(i);  //w->i
            }
        }

        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, inverseAdj, visited);
            }
        }
    }

    /**
     * DEF算法
     * 递归处理每个顶点，先输出顶点vertex依赖的顶点在输出自己
     * @param vertex 顶点
     * @param inverseAdj 逆邻接表
     * @param visited 每个顶点是否访问的数组
     */
    private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
        for (int i = 0; i < inverseAdj[vertex].size(); i++) {
            int w = inverseAdj[vertex].get(i);
            if (visited[w]) continue;
            visited[w] = true;
            dfs(w, inverseAdj, visited);
        }//先把vertex这个顶点可达的所有顶点打印出来在打印他本身

        System.out.print("->" + vertex);
    }
}

class Graph {
    private int v;   //顶点的个数
    private LinkedList<Integer> adj[];  //邻接表

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {  //s先于t，边s->t
        adj[s].add(t);
    }
}

